#ifndef __HEAP_POLICY__
#define __HEAP_POLICY__

#include "heap_policy.hpp" // declares heap_policy
#include <cmath> // defines ilogb
#include <iostream> // defines std::cerr

extern int ilogb  (double) throw();

/*

Specialization for d = 2.
The functions is_first_child, depth, leftmost_leaf, first_child, parent, ancestor, 
maximum_child_some_absent, maximum_child_all_present have been reimplemented.

*/

template <> template <typename position, typename ordering>
heap_policy<2, position, ordering>::heap_policy (
  heap_policy<2, position, ordering>::index n
): n(n) {
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::size () const {
  return n;
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
    heap_policy<2, position, ordering>::last_leaf () const {
  return n - 1;
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::last_child (
  heap_policy<2, position, ordering>::index i
) const { 
  if(((i / 3) * 3) == i) return i + 2;
  else  return 6 * (i - (i / 3)) + 3;
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::first_child (
  heap_policy<2, position, ordering>::index i
) const {
  if(((i / 3) * 3) == i) return i + 1;
  else  return  6 * (i - (i / 3));
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::parent (
  heap_policy<2, position, ordering>::index i
) const {
  //  if(i % 3 == 0) return ((i + 6) / 12 - 1) * 3 + (i / 6 - 1) % 2 + 1;
  //return i - i % 3;
  return 0;
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::top_some_absent (
  position a,
  heap_policy<2, position, ordering>::index i,
  const ordering& less
) const {
  return first_child(i);  
}

template <> template <typename position, typename ordering>
typename heap_policy<2, position, ordering>::index
heap_policy<2, position, ordering>::top_all_present (
  position a,
  heap_policy<2, position, ordering>::index i,
  const ordering& less
) const {
  typedef typename heap_policy<2, position, ordering>::index index;
  index k = i / 3;
  if(3 * k == i)
    return less(a[i + 1], a[i + 2]) ? i + 2 : i + 1;
  k = 6 * (i - k);
  return less(a[k], a[k + 3]) ? k + 3 : k;
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::update_some_absent (
  position a,
  heap_policy<2, position, ordering>::index i,
  const heap_policy<2, position, ordering>::element& x,
  const ordering& less
) {
  a[i] = x;
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::update_all_present (
  position a,
  heap_policy<2, position, ordering>::index i,
  const heap_policy<2, position, ordering>::element& x,
  const ordering&
) {
  a[i] = x;
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::visit_branch_first_time (
  position,
  heap_policy<2, position, ordering>::index,
  const ordering&
) {
  // Does nothing
}

template <> template <typename position, typename ordering>
void
heap_policy<2, position, ordering>::erase_last_leaf (position) {
  --n;
}

#endif // __HEAP_POLICY__

